//给定两个单词 word1 和
// word2 ，返回使得
// word1 和 
// word2 相同所需的最小步数。 
//
// 每步 可以删除任意一个字符串中的一个字符。 
//
// 
//
// 示例 1： 
//
// 
//输入: word1 = "sea", word2 = "eat"
//输出: 2
//解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
// 
//
// 示例 2: 
//
// 
//输入：word1 = "leetcode", word2 = "etco"
//输出：4
// 
//
// 
//
// 提示： 
// 
//
// 
// 1 <= word1.length, word2.length <= 500 
// word1 和 word2 只包含小写英文字母 
// 
//
// Related Topics 字符串 动态规划 👍 582 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution583_1
{
    public int minDistance(String word1, String word2) {
        // 1. 先找出最长公共子序列长度 x
        // 2. 两字符串总长度 - 2x

        return word1.length() + word2.length() - 2 * minSameStrSerialLen(word1, word2);
    }

    public int minSameStrSerialLen(String word1, String word2) {
        int N1 = word1.length();
        int N2 = word2.length();
        int[][] dp = new int[N1+1][N2+1]; // dp[i][j], i-1,j-1 末尾子串时的最长公共子序列
        for (int i = 0; i <= N1; i++) {
            for (int j = 0; j <= N2; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                int r1 = dp[i-1][j-1];
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    r1++;
                }
                int r2 = dp[i][j-1];
                int r3 = dp[i-1][j];

                dp[i][j] = Math.max(r1, Math.max(r2, r3));
            }
        }

        return dp[N1][N2];
    }
}

class Solution583_2
{
    public int minDistance(String word1, String word2) {
        // 直接动态规划
        int N1 = word1.length(), N2 =word2.length();
        int[][] dp = new int[N1+1][N2+1]; // dp[i][j] 考虑 i-1,j-1 位置

        for (int i = 0; i <= N1; i++) {
            for (int j = 0; j <= N2; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = i;
                    continue;
                }

                int r1 = dp[i - 1][j - 1];
                if (word1.charAt(i-1) != word2.charAt(j-1)) {
                    r1 = r1 + 2;
                }
                int r2 = 1 + dp[i - 1][j];
                int r3 = 1 + dp[i][j - 1];

                dp[i][j] = Math.min(r1, Math.min(r2, r3));
            }
        }

        return dp[N1][N2];
    }

}

//leetcode submit region end(Prohibit modification and deletion)

class Test583 {
    public static void main(String[] args) {
        String word1 = "sea";
        String word2 = "eat";
        // int res = new Solution().minDistance(word1, word2);
        // System.out.println(res);
    }
}